#!/usr/bin/env python3

"""
Given a collection of distinct integers, return all possible permutations.
"""

import copy

class Solution:
    def permute(self, nums):
        return self._permute(nums)

    def _permute(self, nums_set):
        if len(nums_set) == 0:
            return [[]]
        result = []
        not_changed = copy.copy(nums_set)
        current_contained = set()
        for num in not_changed:
            if num in current_contained:
                continue
            current_contained.add(num)
            nums_set.remove(num)
            cases = self._permute(nums_set)
            for case in cases:
                case.insert(0, num)
                result.append(case)
            nums_set.insert(0, num)
        return result


if __name__ == '__main__':
    s = Solution()
    result = s.permute([1, 1, 2])
    print(f'result: {result}')

